/**
 * 剑指 Offer 51. 数组中的逆序对
 * https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 */
public class Solutions_Offer_51 {
    public static void main(String[] args) {
        int[] nums = {7, 5, 6, 4};  // output: 5
//        int[] nums = {7, 2, 3, 4, 5, 6};  // output: 5

        int result = reversePairs(nums);
        System.out.println(result);
    }

    /**
     * 解题思路：归并排序
     */
    public static int reversePairs(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int len = nums.length;
        int[] temp = new int[len];
        int left = 0, right = len - 1;
        int res = sort(nums, left, right, temp);
        return res;
    }

    public static int sort(int[] nums, int left, int right, int[] temp) {
        if (left >= right) {
            return 0;
        }
        // 分解为两部分
        int mid = left + (right - left) / 2;
        int leftRes = sort(nums, left, mid, temp);
        int rightRes = sort(nums, mid + 1, right, temp);
        int res = leftRes + rightRes;
        if (nums[mid] <= nums[mid + 1]) {
            // 提前返回：不需要排序，所以没有逆序对
            return res;
        }

        // 左右部分完成排序后，最后完成整体的排序
        // 排序过程中，完成逆序对的数量计算
        int l = left, r = mid + 1, idx = left;
        while (l <= mid && r <= right) {
            if (nums[l] <= nums[r]) {
                // 计算右侧部分，小于当前元素的数量（逆序对）
                res += r - 1 - mid;
                temp[idx] = nums[l ++];
            } else {
                temp[idx] = nums[r ++];
            }
            idx ++;
        }
        while (l <= mid) {
            // 计算右侧部分，小于当前元素的数量（逆序对）
            res += r - 1 - mid;
            temp[idx ++] = nums[l ++];
        }
        while (r <= right) {
            temp[idx ++] = nums[r ++];
        }
        // 将 nums 的 [left, right] 区间中的元素排序后，再转移到 [left, right] 中
        for (int i = left; i <= right; i++) {
            nums[i] = temp[i];
        }
        return res;
    }
}
